{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Brightest Position on Street"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #ordered-set #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #有序集合 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: brightestPosition"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #街上最亮的位置"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>一条街上有很多的路灯，路灯的坐标由数组&nbsp;<code>lights&nbsp;</code>的形式给出。&nbsp;每个&nbsp;<code>lights[i] = [position<sub>i</sub>, range<sub>i</sub>]</code>&nbsp;代表坐标为&nbsp;<code>position<sub>i</sub></code>&nbsp;的路灯照亮的范围为&nbsp;<code>[position<sub>i</sub> - range<sub>i</sub>, position<sub>i</sub> + range<sub>i</sub>]</code>&nbsp;<strong>（包括顶点）。</strong></p>\n",
    "\n",
    "<p>位置&nbsp;<code>p</code>&nbsp;的亮度由能够照到&nbsp;<code>p</code>的路灯的数量来决定的。</p>\n",
    "\n",
    "<p>给出&nbsp;<code>lights</code>, 返回<strong>最亮</strong>的位置&nbsp;。如果有很多，返回坐标最小的。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "<img src=\"https://assets.leetcode.com/uploads/2021/09/28/image-20210928155140-1.png\" style=\"width: 700px; height: 165px;\">\n",
    "<pre><strong>输入:</strong> lights = [[-3,2],[1,2],[3,3]]\n",
    "<strong>输出:</strong> -1\n",
    "<strong>解释:</strong>\n",
    "第一个路灯照亮的范围是[(-3) - 2, (-3) + 2] = [-5, -1].\n",
    "第二个路灯照亮的范围是 [1 - 2, 1 + 2] = [-1, 3].\n",
    "第三个路灯照亮的范围是 [3 - 3, 3 + 3] = [0, 6].\n",
    "\n",
    "坐标-1被第一个和第二个路灯照亮，亮度为2\n",
    "坐标0，1，2都被第二个和第三个路灯照亮，亮度为2.\n",
    "对于以上坐标，-1最小，所以返回-1</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入:</strong> lights = [[1,0],[0,1]]\n",
    "<strong>输出:</strong> 1\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入:</strong> lights = [[1,2]]\n",
    "<strong>输出:</strong> -1\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= lights.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>lights[i].length == 2</code></li>\n",
    "\t<li><code>-10<sup>8</sup> &lt;= position<sub>i</sub> &lt;= 10<sup>8</sup></code></li>\n",
    "\t<li><code>0 &lt;= range<sub>i</sub> &lt;= 10<sup>8</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [brightest-position-on-street](https://leetcode.cn/problems/brightest-position-on-street/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [brightest-position-on-street](https://leetcode.cn/problems/brightest-position-on-street/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[-3,2],[1,2],[3,3]]', '[[1,0],[0,1]]', '[[1,2]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def brightestPosition(self, lights: List[List[int]]) -> int:\n",
    "        diffs = defaultdict(int)\n",
    "        for p, r in lights:\n",
    "            diffs[p-r] += 1\n",
    "            diffs[p+r+1] -= 1\n",
    "        \n",
    "        cur = mx = ans = 0\n",
    "        for p in sorted(diffs): \n",
    "            cur += diffs[p]\n",
    "            if cur > mx:\n",
    "                mx, ans = cur, p \n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def brightestPosition(self, lights: List[List[int]]) -> int:\n",
    "        diff = defaultdict(int)\n",
    "        for p,r in lights:\n",
    "            diff[p-r] += 1\n",
    "            diff[p+r+1] -= 1\n",
    "        d,mx,ans = 0,0,None\n",
    "        for k in sorted(diff.keys()):\n",
    "            d+=diff[k]\n",
    "            if d>mx:\n",
    "                mx,ans = d,k\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def brightestPosition(self, lights: List[List[int]]) -> int:\n",
    "        diff = defaultdict(int)\n",
    "        for p, r in lights:\n",
    "            diff[p - r] += 1\n",
    "            diff[p + r + 1] -= 1\n",
    "        d, mx, ans = 0, 0, None\n",
    "        for k in sorted(diff.keys()):\n",
    "            d += diff[k]\n",
    "            if d > mx:\n",
    "                mx, ans = d, k\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def brightestPosition(self, lights: List[List[int]]) -> int:\n",
    "        diff = defaultdict(int)\n",
    "        for p, r in lights:\n",
    "            diff[p - r] += 1\n",
    "            diff[p + r + 1] -= 1\n",
    "        d, mx, ans = 0, 0, None\n",
    "        for k in sorted(diff.keys()):\n",
    "            d += diff[k]\n",
    "            if d > mx:\n",
    "                mx, ans = d, k\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def brightestPosition(self, lights: List[List[int]]) -> int:\n",
    "        diff = defaultdict(int)\n",
    "        for p, r in lights:\n",
    "            diff[p - r] += 1\n",
    "            diff[p + r + 1] -= 1\n",
    "        d, mx, ans = 0, 0, None\n",
    "        for k in sorted(diff.keys()):\n",
    "            d += diff[k]\n",
    "            if d > mx:\n",
    "                mx, ans = d, k\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def brightestPosition(self, lights: List[List[int]]) -> int:\n",
    "        temp=defaultdict(int)\n",
    "        for i,j in lights:\n",
    "            temp[i-j]+=1\n",
    "            temp[i+j+1]-=1\n",
    "        m,ans,res=0,-inf,0\n",
    "        for i in sorted(temp.keys()):\n",
    "            res+=temp[i]\n",
    "            if res>m:\n",
    "                m=res\n",
    "                ans=i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def brightestPosition(self, lights: List[List[int]]) -> int:\n",
    "        temp=defaultdict(int)\n",
    "        distance=200000000\n",
    "        for i,j in lights:\n",
    "            temp[i-j+distance]+=1\n",
    "            temp[i+j+1+distance]-=1\n",
    "        m,ans,res=0,-inf,0\n",
    "        for i in sorted(temp.keys()):\n",
    "            res+=temp[i]\n",
    "            if res>m:\n",
    "                m=res\n",
    "                ans=i\n",
    "        return ans-distance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def brightestPosition(self, lights: List[List[int]]) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param lights:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        sd1 = SortedList(key=lambda x: (x[0], x[1]))\n",
    "        for i in lights:\n",
    "            cur, radix = i[0], i[1]\n",
    "            sd1.add((cur-radix, cur+radix))\n",
    "        min1 = sd1[0][0]\n",
    "        max1 = sd1[-1][1]\n",
    "        cnt = 0\n",
    "        ans = None\n",
    "        sd2 = SortedList(key=lambda x: (x[1]))\n",
    "        intevallist = []\n",
    "        for i in sd1:\n",
    "            intevallist.append(i[0])\n",
    "            intevallist.append(i[1])\n",
    "        intevallist.sort()\n",
    "        for i in intevallist:\n",
    "            if len(sd1) == 0:\n",
    "                break\n",
    "            while len(sd2) > 0 and sd2[0][1] < i:\n",
    "                sd2.pop(0)\n",
    "            while len(sd1) > 0 and sd1[0][0] <= i:\n",
    "                v1 = sd1.pop(0)\n",
    "                if v1[1] >= i:\n",
    "                    sd2.add(v1)\n",
    "            if len(sd2) > cnt:\n",
    "                cnt = len(sd2)\n",
    "                ans = i\n",
    "\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "a = Solution()\n",
    "print(a.brightestPosition([[1,1],[2,4],[-1,0],[-3,5],[1,2]]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def brightestPosition(self, lights: List[List[int]]) -> int:\n",
    "        cnt = Counter()\n",
    "        for x, y in lights:\n",
    "            cnt[x - y] += 1\n",
    "            cnt[x + y + 1] -= 1\n",
    "        mx, ans, tmp = 0, -inf, 0\n",
    "        for i in sorted(cnt.keys()):\n",
    "            tmp += cnt[i]\n",
    "            if tmp > mx:\n",
    "                mx, ans = tmp, i \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def brightestPosition(self, lights: List[List[int]]) -> int:\n",
    "        temp=defaultdict(int)\n",
    "        distance=0\n",
    "        for i,j in lights:\n",
    "            temp[i-j+distance]+=1\n",
    "            temp[i+j+1+distance]-=1\n",
    "        m,ans,res=0,-inf,0\n",
    "        for i in sorted(temp.keys()):\n",
    "            res+=temp[i]\n",
    "            if res>m:\n",
    "                m=res\n",
    "                ans=i\n",
    "        return ans-distance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 离散化+差分数组\n",
    "    def brightestPosition(self, lights: List[List[int]]) -> int:\n",
    "        diff = defaultdict(int)\n",
    "        for p, r in lights:\n",
    "            diff[p - r] += 1\n",
    "            diff[p + r + 1] -= 1\n",
    "\n",
    "        axis = sorted(list(diff.keys()))\n",
    "\n",
    "        ans = -1\n",
    "        cnt = cur = 0\n",
    "        n = len(axis)\n",
    "        for i in range(n):\n",
    "            diff[axis[i]] += cur\n",
    "            cur = diff[axis[i]]\n",
    "            if cur > cnt:\n",
    "                ans = axis[i]\n",
    "                cnt = cur\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 离散化+差分数组\n",
    "    def brightestPosition(self, lights: List[List[int]]) -> int:\n",
    "        diff = defaultdict(int)\n",
    "        for p, r in lights:\n",
    "            diff[p - r] += 1\n",
    "            diff[p + r + 1] -= 1\n",
    "\n",
    "        axis = sorted(list(diff.keys()))\n",
    "\n",
    "        ans = -1\n",
    "        cnt = cur = 0\n",
    "        n = len(axis)\n",
    "        for i in range(n):\n",
    "            diff[axis[i]] += cur\n",
    "            cur = diff[axis[i]]\n",
    "            if cur > cnt:\n",
    "                ans = axis[i]\n",
    "                cnt = cur\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
